package com.tools.web.work.tree;

import com.tools.common.object.Note;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * 树形数据结构的相关操作工具类
 * */
@Note("树形数据结构的相关操作工具类")
public final class TreeKit {

    private TreeKit() {}


    @Note("将 source 列表里的节点按层级划分，生成新的树形列表返回。时间复杂度 O(n)。" +
            "【注意】：source 列表里的元素的类型，必须与 targetType 类型相同，或者是其子类/实现类。")
    public static <T> List<T> generate(List<? extends TreeNode> source, Class<T> targetType) {
        if(source == null || source.isEmpty()) return new ArrayList<>();
        Map<Object, TreeNode> nodeMap = new HashMap<>((int) (source.size() / 0.75) + 1);
        for (TreeNode node : source) {
            nodeMap.put(node.idGet(), node);
        }
        List<T> result = new ArrayList<>(nodeMap.size());
        for (TreeNode node : source) {
            Object parentId = node.parentIdGet();
            if (parentId == null) {
                result.add((T) node);
                continue;
            }
            TreeNode<?> parentNode = nodeMap.get(parentId);
            if (parentNode != null) {
                parentNode.addChild(node);
            }
        }
        return result;
    }


    @Note("将 childList 按一定的规则将其组合到 parentList 的子集合里")
    public static void compose(List<? extends TreeNode> parentList, List<? extends TreeNode> childList) {
        if(parentList == null || parentList.isEmpty()) return;
        if(childList == null || childList.isEmpty()) return;
        Map<Object, TreeNode> nodeMap = new HashMap<>((int) (parentList.size() / 0.75) + 1);
        for (TreeNode node : parentList) {
            nodeMap.put(node.idGet(), node);
        }
        for (TreeNode node : childList) {
            Object parentId = node.parentIdGet();
            TreeNode parentNode = nodeMap.get(parentId);
            if (parentNode != null) {
                parentNode.addChild(node);
            }
        }
    }
}
